package d6.offer32_3;

import com.jieshen.TreeNode;
import com.jieshen.utils.BinaryTree;

import java.util.*;

public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {

        int i = 1;
        if (root == null)
            return new ArrayList<>();

        Deque<TreeNode> deque = new LinkedList();
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> tmp;
        deque.add(root);
        while (!deque.isEmpty()) {
            tmp = new LinkedList<>();
            int size = deque.size();
            //从左边读取，先存左孩子，右插新数值
            if(i%2==1){
                for (int j = 0; j < size; j++) {
                    TreeNode node = deque.removeFirst();
                    tmp.add(node.val);
                    if(node.left!=null)
                        deque.addLast(node.left);
                    if(node.right!=null)
                        deque.addLast(node.right);
                }
            }else{
                //从右边读取，先存右孩子，左插新数值，
                for (int j = 0; j < size; j++) {
                    TreeNode node = deque.removeLast();
                    tmp.add(node.val);
                    if(node.right!=null)
                        deque.addFirst(node.right);
                    if(node.left!=null)
                        deque.addFirst(node.left);

                }
            }
            res.add(tmp);
            i += 1;
        }
        return res;
    }

    public static void main(String[] args) {
        Integer[] arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99};
        TreeNode treeNode = new BinaryTree().BuildTree(arr);
        List<List<Integer>> lists = new Solution().levelOrder(treeNode);
        for (List<Integer> list : lists) {
            for (Integer integer : list) {
                System.out.print(integer + " ");
            }
            System.out.println();
        }
    }
}
